package org.example.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @version 1.0.0
 * @author: lynn
 * @description:
 * @date: 2021/8/9 8:24
 */
public class LC51 {


    public static void main(String[] args) {
        LC51 lc=new LC51();
        lc.solveNQueens(4);
        System.out.println(lc.res);
    }

    //fixme https://www.bilibili.com/video/BV12z4y1d79e?from=search&seid=8963664169909268765
    private List<List<String>> res=new ArrayList<>();
    private int n;
    private HashSet<Integer> col,pie,na;
    Boolean[][] board;
    public List<List<String>> solveNQueens(int n) {
        board=new Boolean[n][n];
        this.n=n;
        this.col=new HashSet<>();
        this.pie=new HashSet<>();
        this.na=new HashSet<>();
        dfs(0);
        return res;
    }
    private void dfs(int i){
        if (i==n){
            //todo generenate res
            generate();
            return;
        }


        for (int j = 0; j <n ; j++) {
            if (col.contains(j)||na.contains(i+j) || pie.contains(i-j)) continue;
            board[i][j]=true;
            col.add(j);
            na.add(i+j);
            pie.add(i-j);
            dfs(i+1);
            col.remove(j);
            na.remove(i+j);
            pie.remove(i-j);
            board[i][j]=false;
        }
    }

    private void generate(){
        List<String> list=new ArrayList<>();
        for (int i = 0; i <n ; i++) {
            StringBuilder sb=new StringBuilder();
            for (int j = 0; j <n ; j++) {
                if (board[i][j]!=null && board[i][j]){
                    sb.append("Q");
                }else {
                    sb.append(".");
                }
            }
            list.add(sb.toString());
        }
        res.add(new ArrayList<>(list));
    }























    private boolean isValid(char[][] board,int row,int col,char n){
        //不能同行
        for (int i = 0; i <col ; i++) {
            if (board[row][i]==n) return false;
        }
        //不能同列
        for (int i = 0; i < row; i++) {
            if (board[i][col]==n) return false;
        }
       //不能45度斜线
        for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        //不能135度斜线
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}
